package 竞赛.NO_401;

import java.util.Arrays;

/**
 * TODO 100319. 执行操作可获得的最大总奖励 I
 * 创建时间：2024-06-09 11:41
 */
public class 执行操作可获得的最大总奖励I_100319 {
    /**
     * 给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
     *
     * 最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
     *
     * 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
     * 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
     * 以整数形式返回执行最优操作能够获得的 最大 总奖励。
     * @param rewardValues
     * @return
     */
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        return dfs(rewardValues, 0, 0);
    }

    int dfs(int[] rewardValues, int i, int ans) {
        if (i == rewardValues.length) {
            return ans;
        }
        if (ans <= rewardValues[i]) {
            int a = dfs(rewardValues, i + 1, ans);
            int c = Math.max(a, ans);
            ans = dfs(rewardValues, i + 1, ans + rewardValues[i]);
            ans = Math.max(c, ans);
        }
        return ans;
    }
}
